#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void traversal(TreeNode * node, int count){
        if(!node->left && !node->right){
            if(count == 0) {
                res.push_back(path);
                return;
            } else{
                return;
            }
        }

        if(node->left){
            path.push_back(node->left->val);
            traversal(node->left, count - node->left->val);
            path.pop_back();
        }

        if(node->right){
            path.push_back(node->right->val);
            traversal(node->right, count - node->right->val);
            path.pop_back();
        }
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(!root) return res;
        path.push_back(root->val);
        traversal(root, targetSum - root->val);
        return res;
    }
};

//迭代法，较繁琐
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    vector<vector<int>> res;
    if(!root) return res;
    stack<pair<TreeNode *, pair<int, vector<int>>>> st;
    st.push({root, {root->val, {root->val}}});
    vector<int> path;
    while(!st.empty()){
        auto [node, state] = st.top(); // C++17结构化绑定
        auto [curSum, path] = state;
        st.pop();

        if(!node->left && !node->right){
            if(curSum == targetSum) {
                res.push_back(path);
            }
            continue;
        }
            
        if(node->right) {
            vector<int> newPath = path;
            newPath.push_back(node->right->val);
            st.push({node->right, {curSum + node->right->val,newPath}});
        }

        if(node->left){
            vector<int> newPath = path;
            newPath.push_back(node->left->val);
            st.push({node->left, {curSum + node->left->val, newPath}});
        }
    }
    return res;
}